home *** CD-ROM | disk | FTP | other *** search
/ Chip 2007 January, February, March & April / Chip-Cover-CD-2007-02.iso / Pakiet bezpieczenstwa / mini Pentoo LiveCD 2006.1 / mpentoo-2006.1.iso / livecd.squashfs / usr / include / nspr / plhash.h < prev    next >
C/C++ Source or Header  |  2006-04-20  |  7KB  |  166 lines
  1. /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
  2. /* ***** BEGIN LICENSE BLOCK *****
  3.  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
  4.  *
  5.  * The contents of this file are subject to the Mozilla Public License Version
  6.  * 1.1 (the "License"); you may not use this file except in compliance with
  7.  * the License. You may obtain a copy of the License at
  8.  * http://www.mozilla.org/MPL/
  9.  *
  10.  * Software distributed under the License is distributed on an "AS IS" basis,
  11.  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
  12.  * for the specific language governing rights and limitations under the
  13.  * License.
  14.  *
  15.  * The Original Code is the Netscape Portable Runtime (NSPR).
  16.  *
  17.  * The Initial Developer of the Original Code is
  18.  * Netscape Communications Corporation.
  19.  * Portions created by the Initial Developer are Copyright (C) 1998-2000
  20.  * the Initial Developer. All Rights Reserved.
  21.  *
  22.  * Contributor(s):
  23.  *
  24.  * Alternatively, the contents of this file may be used under the terms of
  25.  * either the GNU General Public License Version 2 or later (the "GPL"), or
  26.  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
  27.  * in which case the provisions of the GPL or the LGPL are applicable instead
  28.  * of those above. If you wish to allow use of your version of this file only
  29.  * under the terms of either the GPL or the LGPL, and not to allow others to
  30.  * use your version of this file under the terms of the MPL, indicate your
  31.  * decision by deleting the provisions above and replace them with the notice
  32.  * and other provisions required by the GPL or the LGPL. If you do not delete
  33.  * the provisions above, a recipient may use your version of this file under
  34.  * the terms of any one of the MPL, the GPL or the LGPL.
  35.  *
  36.  * ***** END LICENSE BLOCK ***** */
  37.  
  38. #ifndef plhash_h___
  39. #define plhash_h___
  40. /*
  41.  * API to portable hash table code.
  42.  */
  43. #include <stdio.h>
  44. #include "prtypes.h"
  45.  
  46. PR_BEGIN_EXTERN_C
  47.  
  48. typedef struct PLHashEntry  PLHashEntry;
  49. typedef struct PLHashTable  PLHashTable;
  50. typedef PRUint32 PLHashNumber;
  51. #define PL_HASH_BITS 32  /* Number of bits in PLHashNumber */
  52. typedef PLHashNumber (PR_CALLBACK *PLHashFunction)(const void *key);
  53. typedef PRIntn (PR_CALLBACK *PLHashComparator)(const void *v1, const void *v2);
  54.  
  55. #if defined(XP_OS2_VACPP) && defined(VACPP_FLIP) /* for nsSpaceManager.cpp */
  56. PR_END_EXTERN_C                                  /* and nsHTMLDocument.cpp */
  57. #endif
  58. typedef PRIntn (PR_CALLBACK *PLHashEnumerator)(PLHashEntry *he, PRIntn i, void *arg);
  59.  
  60. #if defined(XP_OS2_VACPP) && defined(VACPP_FLIP)
  61. PR_BEGIN_EXTERN_C
  62. #endif
  63.  
  64. /* Flag bits in PLHashEnumerator's return value */
  65. #define HT_ENUMERATE_NEXT       0       /* continue enumerating entries */
  66. #define HT_ENUMERATE_STOP       1       /* stop enumerating entries */
  67. #define HT_ENUMERATE_REMOVE     2       /* remove and free the current entry */
  68. #define HT_ENUMERATE_UNHASH     4       /* just unhash the current entry */
  69.  
  70. typedef struct PLHashAllocOps {
  71.     void *              (PR_CALLBACK *allocTable)(void *pool, PRSize size);
  72.     void                (PR_CALLBACK *freeTable)(void *pool, void *item);
  73.     PLHashEntry *       (PR_CALLBACK *allocEntry)(void *pool, const void *key);
  74.     void                (PR_CALLBACK *freeEntry)(void *pool, PLHashEntry *he, PRUintn flag);
  75. } PLHashAllocOps;
  76.  
  77. #define HT_FREE_VALUE   0               /* just free the entry's value */
  78. #define HT_FREE_ENTRY   1               /* free value and entire entry */
  79.  
  80. struct PLHashEntry {
  81.     PLHashEntry         *next;          /* hash chain linkage */
  82.     PLHashNumber        keyHash;        /* key hash function result */
  83.     const void          *key;           /* ptr to opaque key */
  84.     void                *value;         /* ptr to opaque value */
  85. };
  86.  
  87. struct PLHashTable {
  88.     PLHashEntry         **buckets;      /* vector of hash buckets */
  89.     PRUint32              nentries;       /* number of entries in table */
  90.     PRUint32              shift;          /* multiplicative hash shift */
  91.     PLHashFunction      keyHash;        /* key hash function */
  92.     PLHashComparator    keyCompare;     /* key comparison function */
  93.     PLHashComparator    valueCompare;   /* value comparison function */
  94.     const PLHashAllocOps *allocOps;     /* allocation operations */
  95.     void                *allocPriv;     /* allocation private data */
  96. #ifdef HASHMETER
  97.     PRUint32              nlookups;       /* total number of lookups */
  98.     PRUint32              nsteps;         /* number of hash chains traversed */
  99.     PRUint32              ngrows;         /* number of table expansions */
  100.     PRUint32              nshrinks;       /* number of table contractions */
  101. #endif
  102. };
  103.  
  104. /*
  105.  * Create a new hash table.
  106.  * If allocOps is null, use default allocator ops built on top of malloc().
  107.  */
  108. PR_EXTERN(PLHashTable *)
  109. PL_NewHashTable(PRUint32 numBuckets, PLHashFunction keyHash,
  110.                 PLHashComparator keyCompare, PLHashComparator valueCompare,
  111.                 const PLHashAllocOps *allocOps, void *allocPriv);
  112.  
  113. PR_EXTERN(void)
  114. PL_HashTableDestroy(PLHashTable *ht);
  115.  
  116. /* Higher level access methods */
  117. PR_EXTERN(PLHashEntry *)
  118. PL_HashTableAdd(PLHashTable *ht, const void *key, void *value);
  119.  
  120. PR_EXTERN(PRBool)
  121. PL_HashTableRemove(PLHashTable *ht, const void *key);
  122.  
  123. PR_EXTERN(void *)
  124. PL_HashTableLookup(PLHashTable *ht, const void *key);
  125.  
  126. PR_EXTERN(void *)
  127. PL_HashTableLookupConst(PLHashTable *ht, const void *key);
  128.  
  129. PR_EXTERN(PRIntn)
  130. PL_HashTableEnumerateEntries(PLHashTable *ht, PLHashEnumerator f, void *arg);
  131.  
  132. /* General-purpose C string hash function. */
  133. PR_EXTERN(PLHashNumber)
  134. PL_HashString(const void *key);
  135.  
  136. /* Compare strings using strcmp(), return true if equal. */
  137. PR_EXTERN(PRIntn)
  138. PL_CompareStrings(const void *v1, const void *v2);
  139.  
  140. /* Stub function just returns v1 == v2 */
  141. PR_EXTERN(PRIntn)
  142. PL_CompareValues(const void *v1, const void *v2);
  143.  
  144. /* Low level access methods */
  145. PR_EXTERN(PLHashEntry **)
  146. PL_HashTableRawLookup(PLHashTable *ht, PLHashNumber keyHash, const void *key);
  147.  
  148. PR_EXTERN(PLHashEntry **)
  149. PL_HashTableRawLookupConst(PLHashTable *ht, PLHashNumber keyHash,
  150.                            const void *key);
  151.  
  152. PR_EXTERN(PLHashEntry *)
  153. PL_HashTableRawAdd(PLHashTable *ht, PLHashEntry **hep, PLHashNumber keyHash,
  154.                    const void *key, void *value);
  155.  
  156. PR_EXTERN(void)
  157. PL_HashTableRawRemove(PLHashTable *ht, PLHashEntry **hep, PLHashEntry *he);
  158.  
  159. /* This can be trivially implemented using PL_HashTableEnumerateEntries. */
  160. PR_EXTERN(PRIntn)
  161. PL_HashTableDump(PLHashTable *ht, PLHashEnumerator dump, FILE *fp);
  162.  
  163. PR_END_EXTERN_C
  164.  
  165. #endif /* plhash_h___ */
  166.